package lcr;

import java.util.Deque;
import java.util.LinkedList;

public class Test0039 {
}

class Solution0039_1 {
    public int largestRectangleArea(int[] heights) {
        int length = heights.length, ans = 0;
        Deque<Integer> deque = new LinkedList<>();
        deque.offer(-1);
        for (int i = 0; i < length; i++) {
            while (deque.peekLast() != -1 && heights[i] < heights[deque.peekLast()]) {
                Integer poll = deque.pollLast();
                ans = Math.max(ans, heights[poll] * (i - deque.peekLast()-1));
            }

            deque.offer(i);
        }

        while (deque.peekLast() != -1) {
            Integer poll = deque.pollLast();
            ans = Math.max(ans, heights[poll] * (length - deque.peekLast()-1));
        }
        return ans;
    }
}